package pl.cba.solgar.game.rogal.utils;

public class BinarySearchTree {
	private BSTNode<?> root;

	public BSTNode<?> getRoot() {
		return root;
	}

	public void addNode(BSTNode<?> node) {
		if (root == null) {
			root = node;
			return;
		}
		BSTNode<?> cnode = root;

		while (true) {
			if (node.getKey() < cnode.getKey()) {
				if (cnode.getLeft() == null) {
					cnode.setLeft(node);
					node.setParent(cnode);
					return;
				}
				else {
					cnode = cnode.getLeft();
				}
			}
			else if (node.getKey() > cnode.getKey()) {
				if (cnode.getRight() == null) {
					cnode.setRight(node);
					node.setParent(cnode);
					return;
				}
				else {
					cnode = cnode.getRight();
				}
			}
			else {
				throw new RuntimeException("BinarySearchTree.addNode: key [" + node.getKey() + "] already in tree!");
			}
		}
	}

	public BSTNode<?> find(int key) {
		BSTNode<?> n = root;
		while (n != null) {
			if (key < n.getKey())
				n = n.getLeft();
			else if (key > n.getKey())
				n = n.getRight();
			else
				break;
		}
		return n;
	}

	public void balance() {
		// implement it :)
	}
}
